package cn.orange.ch07_binarytree;

import cn.orange.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * LC113.路径总和ii
 */
public class LC113 {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> paths = new ArrayList<>();
        if (root == null) return paths;
        LinkedList<Integer> path = new LinkedList<>();
        backtracking(root, path, paths, targetSum);
        return paths;
    }

    private void backtracking(TreeNode root, LinkedList<Integer> path, List<List<Integer>> paths, int targetSum) {
        path.add(root.val);
        if (root.left == null && root.right == null) {
            if (targetSum == root.val) {
                paths.add(new ArrayList<>(path));
            }
            return;
        }
        if (root.left != null) {
            backtracking(root.left, path, paths, targetSum - root.val);
            path.removeLast();
        }
        if (root.right != null) {
            backtracking(root.right, path, paths, targetSum - root.val);
            path.removeLast();
        }
    }

    public static void main(String[] args) {
        LC113 alg = new LC113();
        TreeNode root = new TreeNode(3, new TreeNode(9), new TreeNode(20));
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println(alg.pathSum(root, 30));
    }
}
